package day48_673;

import java.util.Arrays;

/**
 * @ClassName Solution
 * @Description TODO
 * @Author clockTown
 * @Date 2021/6/26 19:24
 * @Version 1.0
 */
public class Solution {

    public int findNumberOfLIS(int[] nums) {
          /*
        对于每一个数nums[i]，看在它之前的数nums[j](0<= j < i)是否比当前数nums[i]小，
        如果nums[i] > nums[j]，那么相当于到nums[j]为止的最长递增子序列长度到nums[i]增加了1，
        到nums[i]为止的最长递增子序列长度就变成了dp[i] = dp[j] + 1
        但是因为满足nums[i] > nums[j] 的nums[j]不止一个，dp[i]应该取这些dp[j] + 1的最大值，并且这些dp[j] + 1还会有相等的情况，
        一旦相等，到nums[i]为止的最长递增子序列个数就应该增加了。
        因此，具体的状态转移如下，在nums[i] > nums[j]的大前提下：
        如果dp[j] + 1 > dp[i]，说明最长递增子序列的长度增加了，dp[i] = dp[j] + 1，长度增加，数量不变 count[i] = count[j]
        如果dp[j] + 1 == dp[i]，说明最长递增子序列的长度并没有增加，但是出现了长度一样的情况，数量增加 count[i] += count[j]
        */
        if(nums.length==0){
            return 0;
        }
        if(nums.length==1){
            return 1;
        }
        // dp数组，代表到nums[i]为止的最长子序列长度
        int[] dp = new int[nums.length];
        // count数组代表到nums[i]为止的最长子序列的个数
        int[] count = new int[nums.length];
        // 另个数组默认初始化都是1，代表最长递增子序列的长度和个数至少为1
        Arrays.fill(dp,1);
        Arrays.fill(count,1);
        // 最大长度初始化为0
        int maxLen = 0;
        // 两层遍历中不断地更新状态
        for(int i = 1; i < nums.length; i++){
            for(int j = 0; j < i; j++){
                // 只有num[i] > num[j] & i > j，才表示有最新的数加入
                if(nums[i] > nums[j]){
                    // 说明前面的状态（长度）+1（代表新加入的数）比当前的长度大
                    // 那么当前长度进行更新，个数没有变化，因此将之前状态替换过来
                    if(dp[j] + 1 > dp[i]){
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    }
                    // 若写if 测试不通过，必须写else if
                    // 说明前面的状态（长度）+1（代表新加入的数）和当前的长度一样，长度不变
                    // 那么就代表着找到了相同长度的序列，更新cout数组
                    else if(dp[j] + 1 == dp[i]){
                        count[i] += count[j];
                    }
                }
            }
            // 更新最大长度
            maxLen = Math.max(maxLen,dp[i]);
        }
        // 遍历
        int res = 0;
        for(int i = 0; i < nums.length; i++){
            // 最大长度和dp[i]相同
            if(maxLen == dp[i]){
                // 将结果和count[i]累加
                res += count[i];
            }
        }
        return res;
    }

}
